home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / llcell.jav < prev    next >
Text File  |  1995-12-14  |  6KB  |  259 lines
  1. /*
  2.   File: LLCell.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.  
  12. */
  13.   
  14. package collections;
  15.  
  16. import java.util.Enumeration;
  17. import java.util.NoSuchElementException;
  18.  
  19. /**
  20.  *
  21.  *
  22.  * LLCells extend Cells with standard linkedlist next-fields,
  23.  * and provide a standard operations on them.
  24.  * <P>
  25.  * LLCells are pure implementation tools. They perform
  26.  * no argument checking, no result screening, and no synchronization.
  27.  * They rely on user-level classes (see for example LinkedList) to do such things.
  28.  * Still, the class is made `public' so that you can use them to
  29.  * build other kinds of collections or whatever, not just the ones
  30.  * currently supported.
  31.  * @author Doug Lea
  32.  * @version 0.93
  33.  *
  34.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  35. **/
  36.  
  37. public class LLCell extends Cell {
  38.   private LLCell next_;
  39.  
  40. /**
  41.  * Return the next cell (or null if none)
  42. **/
  43.  
  44.   public final LLCell next()           { return next_; }
  45.  
  46. /**
  47.  * set to point to n as next cell
  48.  * @param n, the new next cell
  49. **/
  50.  
  51.   public final void  next(LLCell n)    { next_ = n; }
  52.  
  53.   public LLCell(Object v, LLCell n)    { super(v); next_ = n; }
  54.   public LLCell(Object v)              { this(v, null); }
  55.   public LLCell()                      { this(null, null); }
  56.  
  57.  
  58. /**
  59.  * Splice in p between current cell and whatever it was previously 
  60.  * pointing to
  61.  * @param p, the cell to splice
  62. **/
  63.  
  64.   public final void linkNext(LLCell p) { 
  65.     if (p != null)  p.next_ = next_; 
  66.     next_ = p;
  67.   }
  68.  
  69. /**
  70.  * Cause current cell to skip over the current next() one, 
  71.  * effectively removing the next element from the list
  72. **/
  73.  
  74.   public final void unlinkNext()       { 
  75.     if (next_ != null) next_ = next_.next_;
  76.   }
  77.  
  78. /**
  79.  * Linear search down the list looking for element (using Object.equals)
  80.  * @param element to look for
  81.  * @return the cell containing element, or null if no such
  82. **/
  83.  
  84.   public final LLCell find(Object element) {
  85.     for (LLCell p = this; p != null; p = p.next_)
  86.       if (p.element().equals(element)) return p;
  87.     return null;
  88.   }
  89.  
  90. /**
  91.  * return the number of cells traversed to find first occurrence
  92.  * of a cell with element() element, or -1 if not present
  93. **/
  94.  
  95.   public final int index(Object element) {
  96.     int i = 0;
  97.     for (LLCell p = this; p != null; p = p.next_) {
  98.       if (p.element().equals(element)) return i;
  99.       else ++i;
  100.     }
  101.     return -1;
  102.   }
  103.  
  104. /**
  105.  * Count the number of occurrences of element in list
  106. **/
  107.  
  108.   public final int count(Object element) {
  109.     int c = 0;
  110.     for (LLCell p = this; p != null; p = p.next_)
  111.       if (p.element().equals(element)) ++c;
  112.     return c;
  113.   }
  114.  
  115. /**
  116.  * return the number of cells in the list
  117. **/
  118.  
  119.   public final int length() {
  120.     int c = 0;
  121.     for (LLCell p = this; p != null; p = p.next_) ++c;
  122.     return c;
  123.   }
  124.  
  125. /**
  126.  * return the cell representing the last element of the list
  127.  * (i.e., the one whose next() is null
  128. **/
  129.  
  130.   public final LLCell last() {
  131.     LLCell p = this; 
  132.     for ( ; p.next_ != null; p = p.next_) {}
  133.     return p;
  134.   }
  135.  
  136. /**
  137.  * return the nth cell of the list, or null if no such
  138. **/
  139.  
  140.   public final LLCell nth(int n) {
  141.     LLCell p = this;
  142.     for (int i = 0; i < n; ++i) p = p.next_;
  143.     return p;
  144.   }
  145.  
  146.  
  147. /**
  148.  * make a copy of the list; i.e., a new list containing new cells
  149.  * but including the same elements in the same order
  150. **/
  151.  
  152.   public LLCell copyList() {
  153.     LLCell newlist = null;
  154.     try {
  155.       newlist = (LLCell)(clone());
  156.     } catch (CloneNotSupportedException ex) {}      
  157.     LLCell current = newlist;
  158.     for (LLCell p = next_; p != null; p = p.next_) {
  159.       try {
  160.         current.next_ = (LLCell)(p.clone());
  161.       } catch (CloneNotSupportedException ex) {}
  162.       current = current.next_;
  163.     }
  164.     current.next_ = null;
  165.     return newlist;
  166.   }
  167.  
  168. /**
  169.  * Clone is SHALLOW; i.e., just makes a copy of the current cell
  170. **/
  171.  
  172.   protected Object clone() throws CloneNotSupportedException { 
  173.     return new LLCell(element(), next_); 
  174.   }
  175.  
  176. /**
  177.  * Basic linkedlist merge algorithm.
  178.  * Merges the lists head by fst and snd with respect to cmp
  179.  * @param fst head of the first list
  180.  * @param snd head of the second list
  181.  * @param cmp a Comparator used to compare elements
  182.  * @return the merged ordered list
  183. **/
  184.  
  185.   public static LLCell merge(LLCell fst, LLCell snd, Comparator cmp) {
  186.     LLCell a = fst;
  187.     LLCell b = snd;
  188.     LLCell hd = null;
  189.     LLCell current = null;
  190.     for (;;) {
  191.       if (a == null) {
  192.         if (hd == null) hd = b; else current.next(b);
  193.         return hd;
  194.       }
  195.       else if (b == null) {
  196.         if (hd == null) hd = a; else current.next(a);
  197.         return hd;
  198.       }
  199.       int diff = cmp.compare(a.element(), b.element());
  200.       if (diff <= 0) {
  201.         if (hd == null) hd = a; else current.next(a);
  202.         current = a;
  203.         a = a.next();
  204.       }
  205.       else {
  206.         if (hd == null) hd = b; else current.next(b);
  207.         current = b;
  208.         b = b.next();
  209.       }
  210.     }
  211.   }
  212.  
  213. /**
  214.  * Standard list splitter, used by sort.
  215.  * Splits the list in half. Returns the head of the second half
  216.  * @param s the head of the list
  217.  * @return the head of the second half
  218. **/
  219.  
  220.   public static LLCell split(LLCell s) {
  221.     LLCell fast = s;
  222.     LLCell slow = s;
  223.  
  224.     if (fast == null || fast.next() == null) return null;
  225.  
  226.     while (fast != null) {
  227.       fast = fast.next();
  228.       if (fast != null && fast.next() != null) {
  229.         fast = fast.next();
  230.         slow = slow.next();
  231.       }
  232.     }
  233.  
  234.     LLCell r = slow.next();
  235.     slow.next(null);
  236.     return r;
  237.  
  238.   }
  239.  
  240. /**
  241.  * Standard merge sort algorithm
  242.  * @param s the list to sort
  243.  * @param cmp, the comparator to use for ordering
  244.  * @return the head of the sorted list
  245. **/
  246.  
  247.   public static LLCell mergeSort(LLCell s, Comparator cmp) {
  248.     if (s == null || s.next() == null) return s;
  249.     else {
  250.       LLCell right = split(s);
  251.       LLCell left = s;
  252.       left  = mergeSort(left, cmp);
  253.       right = mergeSort(right, cmp);
  254.       return merge(left, right, cmp);
  255.     }
  256.   }
  257.  
  258. }
  259.